package com.example.leetcode.prcatice;

/**
 * 给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
 *
 * 全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
 *
 * 0 <= i < j < n
 * nums[i] > nums[j]
 * 局部倒置 的数目等于满足下述条件的下标 i 的数目：
 *
 * 0 <= i < n - 1
 * nums[i] > nums[i + 1]
 * 当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/global-and-local-inversions
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test775 {

    /**
     * 局部倒置一定是全部倒置，但全局倒置不一定是局部倒置
     * @param nums
     * @return
     */
    public boolean isIdealPermutation(int[] nums) {
        int len = nums.length;
        int max = nums[len -1];
        for (int i = len -3;i>=0;i--) {
            int num = nums[i];
            if (num > max) {
                return false;
            }
            max = Math.min(nums[i + 1] ,max);
        }
        return true;
    }


    public static void main(String[] args) {
        Test775 t = new Test775();
        int[] nums = {1,2,0};
        System.out.println(t.isIdealPermutation(nums));
    }
}
